package myself.a014Recursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author 叶之越
 * Description
 * Date 2021/2/2
 * Time 14:11
 * Mail 739153436@qq.com
 */
public class PrintAllSubsquences {
    public static List<String> subs(String s) {
        char[] str = s.toCharArray();
        // 这个递归不需要从下往上拿信息，所有可以设置返回值是void
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }

    // 打印一个字符串的全部子序列
    private static void process1(char[] arr, int len, List<String> ans, String path) {
        if (len == arr.length) {
            ans.add(path);
            return;
        }
        process1(arr, len + 1, ans, path + arr[len]);
        process1(arr, len + 1, ans, path);
    }

    // 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
    private static void process2(char[] arr, int len, HashSet<String> ans, String path) {
        if (len == arr.length) {
            ans.add(path);
            return;
        }
        process2(arr, len + 1, ans, path + arr[len]);
        process2(arr, len + 1, ans, path);
    }


}
